个人计算机知识展示

Appearance

list 链表 ​

list底层是双向循环链表，因此不支持随机访问，但对于插入和删除能做到 O(1)的复杂度，且插入和删除不会使迭代器失效。

  • 基本语法
    list<typename> name;

    需要加上头文件 list

例如：

c
//表示创建一个int类型的链表，名字叫做l
list<int> l;

list 的常用函数 ​

构造和赋值 ​

  • 创建一个空的 list

list<int> L1;
创建一个空的整数类型的链表，名字叫做 L1

  • 创建一个大小为 n，值都为 0 的 list

list<int> L1(10, 0);
创建一个大小为 10，值为 0 的整数类型的链表，名字叫做 L1

  • 创建一个和 L1 一样的 list

list<int> L2(L1);
创建一个跟 L1 一样的整数类型的链表 L2

  • push_back()

L1.push_back(num)
从链表 L1 的末尾插入一个值 num

  • push_front()

L1.push_front(num)
从链表 L1 的头部插入一个值 num

大小、容量 ​

  • 返回 List 中元素的个数

L1.size()
返回链表 L1 中的元素个数

size 示例代码
cpp
#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1(10,1);
	cout << "L1链表中共有 " << L1.size() << " 个元素" << endl;
    return 0;
}

运行结果：
```c
L1链表中共有 10 个元素
  • 返回容器所能容纳的最大元素数目

L1.max_size()
返回 L1 所能容纳的最大元素数目

是系统或者库所实施的限制,但是容器不一定保证能达到该大小，有可能在还未达到该大小的时候，就已经无法继续分配任何的空间了。

  • 判断链表是否为空

L1.empty()
判断 L1 链表是否为空，如果为空则返回 True，否则返回 False

遍历 ​

遍历 示例代码
cpp
#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);
	L1.push_back(50);
    //list<int>::iterator可以用auto代替
	for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
		cout << *it << &apos; &apos; ;
	}
    return 0;
}

运行结果：

c
10 20 30 40 50

插入 ​

  • 在指定位置插入一个元素

L1.insert(L1.begin()+num,value);
在链表的开头位置插入值为 value 的元素

在指定位置插入一个元素 示例代码
cpp
#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);
	L1.push_back(50);
	cout << "插入元素之前：" << endl;
	for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
		cout << *it << &apos; &apos; ;
	}
	cout << endl;
	L1.insert(L1.begin(),100);
	cout << "插入元素之后：" << endl;
	for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
		cout << *it << &apos; &apos; ;
	}
    return 0;
}

运行结果：

c
插入元素之前：
10 20 30 40 50
插入元素之后：
100 10 20 30 40 50

分析

表示在链表的开头插入一个元素 100

  • 在指定位置插入多个元素 L1.insert(L1.begin(), n, value);
    在链表的开头位置插入值为 num 的 n 个元素
在指定位置插入多个元素 示例代码
cpp
#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);
	L1.push_back(50);
	cout << "插入元素之前：" << endl;
	for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
		cout << *it << &apos; &apos; ;
	}
	cout << endl;
	L1.insert(L1.begin(),3,100);
	cout << "插入元素之后：" << endl;
	for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
		cout << *it << &apos; &apos; ;
	}
    return 0;
}

运行结果：

c
插入元素之前：
10 20 30 40 50
插入元素之后：
100 100 100 10 20 30 40 50

分析

表示在链表的开头插入 3 个都是 100 的值

删除 ​

  • 在头部删除元素 L1.pop_front();
    删除 L1 链表的头部元素
在头部删除元素 示例代码
cpp
#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);
	L1.push_back(50);
		cout << "删除元素之前：" << endl;
	for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
		cout << *it << &apos; &apos; ;
	}
	cout << endl;
	L1.pop_front();
	cout << "删除元素之后：" << endl;
	for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
		cout << *it << &apos; &apos; ;
	}
    return 0;
}

运行结果：

c
删除元素之前：
10 20 30 40 50
删除元素之后：
20 30 40 50

分析

将链表的头部元素 10 删除了

  • 在尾部删除元素 L1.pop_back();
    删除 L1 链表的尾部元素
在尾部删除元素 示例代码
cpp
#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1;
	L1.push_back(10);
	L1.push_back(20);
	L1.push_back(30);
	L1.push_back(40);
	L1.push_back(50);
		cout << "删除元素之前：" << endl;
	for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
		cout << *it << &apos; &apos; ;
	}
	cout << endl;
	L1.pop_back() ;
	cout << "删除元素之后：" << endl;
	for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
		cout << *it << &apos; &apos; ;
	}
    return 0;
}

运行结果：

c
删除元素之前：
10 20 30 40 50
删除元素之后：
10 20 30 40

分析

将链表的尾部元素 50 删除了

  • 删除任意位置上的一个元素 L8.erase(++L8.begin());

排序 ​

  • 通过 list 的 sort 成员函数来排序。默认从低到高

L1.sort();
对链表 L1 进行排序

升序 示例代码
cpp
#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1;
	L1.push_back(10);
	L1.push_back(30);
	L1.push_back(20);
	L1.push_back(70);
	L1.push_back(50);
	cout << "排序之前：" << endl;
	for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
		cout << *it << &apos; &apos; ;
	}
	cout << endl;
	L1.sort();
	cout << "排序之后：" << endl;
	for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
		cout << *it << &apos; &apos; ;
	}
    return 0;
}

运行结果：

c
排序之前：
10 30 20 70 50
排序之后：
10 20 30 50 70

分析

链表里面的元素默认升序排序

  • 通过 list 的 sort 成员函数来排序。默认从低到高

L1.sort(greater<int>());
对链表 L1 进行降序排序

降序 示例代码
cpp
#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1;
	L1.push_back(10);
	L1.push_back(30);
	L1.push_back(20);
	L1.push_back(70);
	L1.push_back(50);
	cout << "排序之前：" << endl;
	for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
		cout << *it << &apos; &apos; ;
	}
	cout << endl;
	L1.sort(greater<int>());
	cout << "排序之后：" << endl;
	for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
		cout << *it << &apos; &apos; ;
	}
    return 0;
}

运行结果：

c
排序之前：
10 30 20 70 50
排序之后：
70 50 30 20 10

分析

链表里面的元素默认降序排序